#include <stdio.h>
#include <stdlib.h>

typedef char DataType;
typedef struct qnode
{
    DataType data;
    struct qnode *next;
} QueueNode;

typedef struct
{
    QueueNode *front;   //对头指针
    QueueNode *rear;    //队尾指针
}LinkQueue;

void InitQueue(LinkQueue *Q)
{
    Q->front = (QueueNode *)malloc(sizeof(QueueNode));
    Q->rear = Q->front;
    Q->rear->next = NULL;
}

int QueueEmpty(LinkQueue *)
{
    return Q->rear == Q->front;
}
void EnQueue(LinkQueue *Q, DataType x)
{
    QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
    p->data = x;
    p->next = NULL;
    Q->rear->next = p; //结点p连接到队尾结点之后
    Q->rear = p; //队尾指针指向新的队尾结点
}

DataType GetFront(LinkQueue *Q)
{
    if(QueueEmpty(Q)){
        printf("empty");
        exit(0);
    }else{
        return Q->front->next->data;
    }
}

DataType DeQueue(LinkQueue *Q)
{
    QueueNode *p;
    if (QueueEmpty(Q)){
        printf("queue underflow");
        exit(0); //出错退出
    }else{
        p = Q->front;
        Q->front = Q->front->next; //原对头结点当头结点（头指针指向下一个结点）
        free(p);
        return (Q->front->data); //返回原队头结点。
    }
}

int main()
{
    LinkQueue Q;
    InitQueue(&Q);
    EnQueue(&Q, 'a');
    EnQueue(&Q, 'b');
    EnQueue(&Q, 'c');
    putchar(GetFront(&Q));
    putchar(DeQueue(&Q));
    putchar(DeQueue(&Q));
    putchar(DeQueue(&Q));
    return 0;
}